#!/usr/bin/env python
# -*- encoding: utf-8 -*-
"""
@File    : search.py
@Time    : 2022/11/20 13:57:43
@Author  : 郭瑞强
@Contact : sunraing@126.com
@Version : 0.1
@License : BSD 3-Clause License
@Desc    : 查找算法
"""


# 无序查找
def sequential_search(lis, key):
    for idx, k in enumerate(lis):
        if k == key:
            return idx
    return -1


# 有序查找
def ordered_sequential_search(lis, key):
    for idx, k in enumerate(lis):
        if k == key:
            return idx
        elif k > key:
            return -1


# 二分查找
def binary_search(lis, key):
    left = 0
    right = len(lis) - 1

    while left <= right:
        mid = (left + right) // 2
        if lis[mid] == key:
            return mid
        else:
            if key < lis[mid]:
                right = mid - 1
            else:
                left = mid + 1

    return -1
